/*
无向图数据结构与算法
*/

#include "Graph.h"
#include <stdio.h>
#include <stdlib.h>

struct _node {
    int vertex;
    struct _node* next;
};

struct Graph {
    int NumberOfVertex;
    int NumberOfEdge;
    pNode arr;  //邻接表为Node数组
};

static void Append(pNode pN, int v);
static void dfs(pGraph pG, int v, int* marked);

void TestGraph() {
    printf("Hello, Graph!\n");
    pGraph pG = Initilize(7);

    AddEdge(pG, 0, 1);
    AddEdge(pG, 0, 2);
    AddEdge(pG, 0, 6);
    AddEdge(pG, 0, 5);
    AddEdge(pG, 3, 5);
    AddEdge(pG, 3, 4);
    AddEdge(pG, 5, 4);
    AddEdge(pG, 6, 4);
    AddEdge(pG, 0, 0);

    PrintGraph(pG);

    printf("VNum=%d,\tENum=%d\n", VNum(pG), ENum(pG));
    for (int i = 0; i < pG->NumberOfVertex; i++) {
        printf("The Degree of %dth vertex=%d\n", i, Degree(pG, i));
    }
    printf("The maximum degree=%d\n", MaxDegree(pG));
    printf("The average degree=%.3lf\n", AveDegree(pG));
    printf("The number of selfloops=%d\n", NumOfSelfLoops(pG));

    DFS(pG, 0);

    Dispose(pG);
}

//初始化图结构
pGraph Initilize(int capacity) {
    pGraph pG = (pGraph)malloc(sizeof(struct Graph));
    pG->NumberOfEdge = 0;
    pG->NumberOfVertex = capacity;

    //初始化数组
    pG->arr = (pNode)malloc(sizeof(struct _node) * capacity);
    //初始化每个元素
    for (int i = 0; i < capacity; i++) {
        pG->arr[i].next = NULL;
        pG->arr[i].vertex = -1;
    }

    return pG;
}

//清理图结构
void Dispose(pGraph pG) {
    if (pG) {
        free(pG->arr);
        free(pG);
    }
}

int VNum(pGraph pG) {
    if (!pG)
        return 0;
    return pG->NumberOfVertex;
}

int ENum(pGraph pG) {
    if (!pG)
        return 0;
    return pG->NumberOfEdge;
}

static void Append(pNode pN, int v) {
    pNode temp = pN;
    while (temp && temp->next)
        temp = temp->next;
    pNode newNode = (pNode)malloc(sizeof(struct _node));
    newNode->next = NULL;
    newNode->vertex = v;
    temp->next = newNode;
}

void AddEdge(pGraph pG, int v1, int v2) {
    //可以添加自环、平行边、重复添加相同边
    if (!pG)
        return;
    if (v1 >= pG->NumberOfVertex || v2 >= pG->NumberOfVertex)
        return;
    Append(&(pG->arr[v1]), v2);
    //若添加自环，仅添加一个，不添加两次
    if (v1 != v2)
        Append(&(pG->arr[v2]), v1);
    pG->NumberOfEdge++;
}

int Degree(pGraph pG, int v) {
    if (!pG)
        return 0;
    int degree = 0;
    pNode temp = &(pG->arr[v]);
    while (temp->next) {
        temp = temp->next;
        degree++;
    }
    return degree;
}

int MaxDegree(pGraph pG) {
    int maxDegree = 0;
    int temp;
    for (int i = 0; i < pG->NumberOfVertex; i++) {
        temp = Degree(pG, i);
        if (temp > maxDegree)
            maxDegree = temp;
    }
    return maxDegree;
}

double AveDegree(pGraph pG) {
    return pG->NumberOfEdge * 2.0 / pG->NumberOfVertex;
}

int NumOfSelfLoops(pGraph pG) {
    int selfloops = 0;
    for (int i = 0; i < pG->NumberOfVertex; i++) {
        pNode temp = &(pG->arr[i]);
        while (temp->next) {
            temp = temp->next;
            if (temp->vertex == i)
                selfloops++;
        }
    }
    return selfloops;
}

void PrintGraph(pGraph pG) {
    if (!pG)
        return;

    printf("\n///////////////////////////////////////////////\n");
    printf("There is %d vertices, %d edges.\n", pG->NumberOfVertex,
           pG->NumberOfEdge);
    for (int i = 0; i < pG->NumberOfVertex; i++) {
        printf("%d: ", i);
        pNode temp = &(pG->arr[i]);
        while (temp->next) {
            temp = temp->next;
            printf("\t%d", temp->vertex);
        }
        printf("\n");
    }
    printf("///////////////////////////////////////////////\n");
}

static void dfs(pGraph pG, int v, int* marked) {
    //如果该元素已经被访问过，就不再访问
    if (marked[v])
        return;
    marked[v] = 1;
    printf("%d→", v);
    pNode temp = &(pG->arr[v]);
    while (temp->next) {
        temp = temp->next;
        dfs(pG, temp->vertex, marked);
    }
}

void DFS(pGraph pG, int v) {
    int* marked = (int*)malloc(sizeof(int) * pG->NumberOfVertex);
    for (int i = 0; i < pG->NumberOfVertex; i++)
        marked[i] = 0;
    printf("The DFS result is:\t");
    dfs(pG, v, marked);
    free(marked);
}